package interview;

import java.util.Stack;

public class interview_08_14 {
    class Solution {
        public int countEval(String s, int result) {
            int n=(s.length()+1)/2;
            int length=s.length();
            int[][][] dp=new int[length][length][2];//dp[i][j][r]索引i到j为r的个数
            for(int i=0;i<length;i+=2){//初始化
                if(s.charAt(i)=='1')dp[i][i][1]=1;
                if(s.charAt(i)=='0')dp[i][i][0]=1;
            }
            for(int d=2;d<length;d+=2){
                for(int i=0;i+d<length;i++){//距离
                    for(int k=0;k<d;k+=2){//对于每段进行遍历
                        char ch=s.charAt(i+k+1);
                        if(ch=='&'){
                            dp[i][i+d][1]+=dp[i][i+k][1]*dp[i+k+2][i+d][1];
                            dp[i][i+d][0]+=dp[i][i+k][0]*dp[i+k+2][i+d][1]+dp[i][i+k][1]*dp[i+k+2][i+d][0]+dp[i][i+k][0]*dp[i+k+2][i+d][0];
                        }
                        if(ch=='|'){
                            dp[i][i+d][0]+=dp[i][i+k][0]*dp[i+k+2][i+d][0];
                            dp[i][i+d][1]+=dp[i][i+k][1]*dp[i+k+2][i+d][0]+dp[i][i+k][0]*dp[i+k+2][i+d][1]+dp[i][i+k][1]*dp[i+k+2][i+d][1];
                        }
                        if(ch=='^'){
                            dp[i][i+d][0]+=dp[i][i+k][0]*dp[i+k+2][i+d][0]+dp[i][i+k][1]*dp[i+k+2][i+d][1];
                            dp[i][i+d][1]+=dp[i][i+k][1]*dp[i+k+2][i+d][0]+dp[i][i+k][0]*dp[i+k+2][i+d][1];
                        }
                    }
                }
            }
            return dp[0][length-1][result];
        }
    }
}
